package com.hc.programming.tree;

import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * <p>
 * 示例 1：
 * <a href="./对称二叉树-示例1.png">示例1</a>
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 * 示例 2：
 * 输入：root = [1,2,2,null,3,null,3]
 * 输出：false
 * <p>
 * 提示：
 * 树中节点数目在范围 [1, 1000] 内
 * -100 <= Node.val <= 100
 * <p>
 * 进阶：你可以运用递归和迭代两种方法解决这个问题吗？
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/9/11 20:52
 */
public class 对称二叉树 {
    public static void main(String[] args) {
        Integer[] arr = new Integer[]{1, 2, 2, 3, 4, 4, 3};
        TreeNode tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isSymmetric(tree));
        arr = new Integer[]{1, 2, 2, null, 3, null, 3};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isSymmetric(tree));
        arr = new Integer[]{1, 2, 2, 2, null, 2};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isSymmetric(tree));
        arr = new Integer[]{1, 1, 1, 1, 1};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=false,--" + isSymmetric(tree));
        arr = new Integer[]{2, 3, 3, 4, 5, 5, 4, null, null, 8, 9, 9, 8};
        tree = TreeNode.tree(arr);
        System.out.println(Arrays.toString(arr) + "=true,--" + isSymmetric(tree));
    }

    public static boolean isSymmetric(TreeNode root) {
//        return 递归(root);
        return 迭代(root);
    }

    private static boolean 迭代(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        if (root == null) return true;
        queue.offer(root.left);
        queue.offer(root.right);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (node1 == null && node2 == null) continue;
            if (node1 == null || node2 == null) return false;
            if (node1.val != node2.val) return false;
            if (node1.left != null || node2.right != null) {
                queue.offer(node1.left);
                queue.offer(node2.right);
            }
            if (node1.right != null || node1.left != null) {
                queue.offer(node1.right);
                queue.offer(node2.left);
            }
        }
        return true;
    }

    private static boolean 递归(TreeNode root) {
        if (root == null) return true;
        return compare(root.left, root.right);
    }

    /**
     * 对称比较
     */
    private static boolean compare(TreeNode node1, TreeNode node2) {
        if (node1 == null && node2 == null) return true;
        if (node1 == null || node2 == null) return false;
        if (node1.val != node2.val) return false;
        return compare(node1.left, node2.right) && compare(node1.right, node2.left);
    }

}
